package com.example.algorithm.service.impl;

import com.example.algorithm.service.TwoPointService;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @auth Administrator
 * @create @2024/7/20@14:02
 * @decription
 * 双指针
 * 定义：双指针是指在算法中同时使用两个指针来追踪数组或序列中的元素位置。这两个指针可以朝着相同方向移动，也可以朝着相反方向移动。
 * 在算法问题中，双指针通常用于在数组、链表或其他数据结构中执行一些特定的操作，如搜索、遍历、或找出满足条件的子序列等。
 * 例子：
 * 1)快慢指针: 两个指针以不同的速度移动。快指针可能每次移动两步，而慢指针每次移动一步。这种模式常用于检测循环或链表中的环。
 * 2)左右指针: 两个指针分别从数组的两端开始移动，逐渐向中间靠拢。这种模式常用于在有序数组中查找特定的元素，或解决一些数组中的问题。
 * 3)滑动窗口:两个指针构成一个窗口，通过移动窗口来执行某种操作。这种模式常用于解决子数组或子字符串的问题。
 * 创建两个指针i和j，其中i从小到大遍历，j从大到小遍历，循环遍历，直到满足调整返回
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 * 1解题思路
 * 定义两个指针，移动方向不同，直到遍历完所有解
 * * 2复杂度分析
 *  *1)时间复杂度：O(N)
 *  *2)空间复杂度：O(N)
 *
 *
 **/
@Slf4j
@Service
public class TwoPointServiceImpl implements TwoPointService {

    /**
     * NO.4移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     *
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * 解题思路：
     * 1)没有非零都往前移动，后面的补零
     * 2)非零放左边，零放右边
     * 解法一：双指针
     * 解法二：偏移量
     * 解法三：快慢指针
     * @param nums
     */

    @Override
    public void moveZeroes(int[] nums) {
        int j=0;
       for(int i=0;i<nums.length;i++){
           if(nums[i]!=0){
               int temp =  nums[i];
               nums[i] = nums[j];
               nums[j]= temp;
               j++;
           }
       }

    }


    /**
     * NO.5 盛最多水的容器
     给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

     找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     *解法一：双指针
     * @param height
     * @return
     */
    @Override
    public int maxArea(int[] height) {
        int length = height.length;
        int left = 0;
        int right = length-1;
        int maxArea = 0;
         while (left <right){
             int area = (right-left)*(Math.min(height[right],height[left]));
             log.info("left:{},right:{},area:{}",left,right,area);
             maxArea = Math.max(maxArea,area);
             if(height[left]<height[right]){
                 left++;
             }else{
                 right--;
             }
         }
        return maxArea;
    }

    /**
     * NO.6三数之和
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     *
     * 你返回所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     * 解法一：排序 + 双指针
     * 解法二：暴力搜索法
     *
     *
     *
     * @param nums
     * @return
     */
    @Override
    public List<List<Integer>> threeSum(int[] nums) {
        int i=0;
        int left=0;
        int right=0;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(i=0;i<nums.length;i++){
            // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(nums[i] > 0){
                break;
            }
            //去重
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            left = i+1;
            right = nums.length-1;
            while(left<right){
             if(nums[i]+nums[left]+nums[right]==0){
                 List<Integer> temp = new ArrayList<>();
                 temp.add(nums[i]);
                 temp.add(nums[left]);
                 temp.add(nums[right]);
                 res.add(temp);
                 left++;
                 right--;
                 while (nums[left]==nums[left -1]&& left<right){//去重
                     left ++;
                 }
                 while (nums[right]==nums[right+1]&& left<right){//去重
                     right--;
                 }

             }else if(nums[i]+nums[left]+nums[right]<0){//去重
                 left++;
             }
             else{//去重
                 right--;
             }
            }
        }



        return res;
    }

    /**
     *  NO.7 接雨水
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * @param height
     * @return
     *解法一：双指针
     * 解法二：动态规划
     * 解法三：单调栈
     * 解法四：按照行求值
     * 解法五：按照列求值
     *
     */
    @Override
    public int trap(int[] height) {
        int length = height.length;
        int left = 0;
        int right = length-1;
        int maxArea = 0;
        int leftMax =0;
        int rightMax =0;
        while (left <=right){
            leftMax = Math.max(leftMax,height[left]);
            rightMax = Math.max(rightMax,height[right]);
            if(leftMax>rightMax){
                maxArea+=rightMax -height[right];
                --right;
            }else{
                maxArea+= leftMax-height[left];
                ++left;
            }
        }
        return maxArea;
    }
}
